//
//  LinkList.swift
//  DataStructuresAlgorithms
//
//  Created by xiangzuhua on 2021/3/16.
//


public class Node<Value>{
    var value: Value
    var next: Node?
    init(value:Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

extension Node:CustomStringConvertible {
    
    public var description: String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing: next)
    }
}

public struct LinkList<Value>{
    var head: Node<Value>?
    var tail: Node<Value>?
    init() {
        
    }
    
    func isEmpty() -> Bool {
        return head == nil
    }
}
    
extension LinkList:CustomStringConvertible {
    public var description:String {
        guard let head = head else {
            return "Empty list"
        }
        
        return String(describing: head)
    }
}


extension LinkList{
    public func size() -> Int{
        guard !isEmpty() else {
            return 0
        }
        var count = 1
        var current = head
        
        while current !== tail {
            count += 1
            current = current?.next
        }
        
        return count
    }
    // 根据下标获取节点
    public func get(index: Int) -> Value?{
        guard index < self.size() else {
            return nil
        }
        
        if index == 0 {
            return head?.value
        }
        
        var count = 1
        var current = head?.next
        while count != index {
            count += 1
            current = current?.next
        }
        return current?.value
    }
}

// 添加节点
extension LinkList{
    // 从头部添加
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    // 从尾部添加
    public mutating func append(_ value: Value) {
        guard !isEmpty() else {
            push(value)
            return
        }
        tail?.next = Node(value: value)
        tail = tail?.next
    }
    
    // 指定位节点后置插入
    @discardableResult
    public mutating func insert(_ value:Value, after node: Node<Value>) -> Node<Value>{
        guard tail !== node else {
            append(value)
            return tail!
        }
        node.next = Node(value:value, next: node.next)
        return node.next!
    }
    
    // 只有空list或者index超过边界才会返回nil
    public func node(at index: Int) -> Node<Value>?{
        var currentNode = head
        var currentIndex = 0
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
        
    }
}


// 删除节点
extension LinkList{
    // 从表头删除
    @discardableResult
    public mutating func pop() -> Value? {
        
        defer {
            head = head?.next
            if isEmpty() {
                tail = nil
            }
        }
        return head?.value
    }
    
    // 从结尾处删除
    @discardableResult
    public mutating func removeLast() -> Value?{
        //
        guard let head = head else {
            return nil
        }
        // 只有一个元素的情况
        guard head.next != nil else {
            return pop()
        }
        
        var prev = head
        var current = head.next
        
        while current?.next != nil {
            prev = prev.next!
            current = current?.next
        }
        prev.next = nil
        tail = prev
        return current?.value
    }
    
    // 删除指定节点的后一个节点
    @discardableResult
    public mutating func remove(after node:Node<Value>) -> Value?{
        defer {
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
    
    // 删除指定的节点
    @discardableResult
    public mutating func remove(at node:Node<Value>) -> Bool{
        
        // 删除的是头部节点
        if head === node {
            head = nil
            tail = nil
            return true
        }
        
        // 取到删除节点的上一个节点
        var prev = head
        var current = head?.next
        while current !== node && current != nil{
            prev = current
            current = current?.next
        }
        
        // 没有这个节点
        guard current != nil else {
            return false
        }
        
        // 删除的是尾部节点
        guard current !== tail else {
            prev?.next = nil
            tail = prev
            return true
        }
        prev?.next = current?.next
        return true
    }
    
    // 删除指定节点的上一个节点
    @discardableResult
    public mutating func remove(front node: Node<Value>) -> Value?{
        // 只有一个节点
        guard head !== tail && head != nil && head !== node else {
            return nil
        }
        // 为空
        guard head != nil else {
            return nil
        }
        // 第一个节点为指定节点的情况
        guard head !== node else {
            return nil
        }
        // 第二个节点为指定节点
        if head?.next === node {
            defer {
                head = head?.next
            }
            return head?.value
        }
        
        // 找到指定节点的前节点
        var prev = head
        var current = head?.next?.next
        while current !== node  && current != nil{
            prev = prev?.next
            current = current?.next
        }
        // 没找到有该节点
        guard current != nil  else {
            return nil
        }

        defer {
            prev?.next = current
        }
        return prev?.next?.value
    }
}

